package com.gitee.ywj1352.leecode;

/**
 * @author wenjie.yang on 2019/10/9.
 */
public class MergeSort {
    private int num = 0; // 全局变量或者成员变量

    public int count(int[] a, int n) {
        num = 0;
        mergeSortCounting(a, 0, n - 1);
        return num;
    }

    private void mergeSortCounting(int[] a, int p, int r) {
        if (p >= r) return;
        int q = (p + r) / 2;
        mergeSortCounting(a, p, q);
        mergeSortCounting(a, q + 1, r);
        merge(a, p, q, r);
    }
    //p  start  q half  r end
    private void merge(int[] a, int p, int q, int r) {
        int i = p, j = q + 1, k = 0;
        int[] tmp = new int[r - p + 1];
        while (i <= q && j <= r) {
            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                num += (q - i + 1); // 统计 p-q 之间，比 a[j] 大的元素个数
                tmp[k++] = a[j++];
            }
        }
        while (i <= q) { // 处理剩下的
            tmp[k++] = a[i++];
        }
        while (j <= r) { // 处理剩下的
            tmp[k++] = a[j++];
        }
        for (i = 0; i <= r - p; ++i) { // 从 tmp 拷贝回 a
            a[p + i] = tmp[i];
        }
    }

    private void merge2(int[] a, int left, int m, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = m+1, k = 0;
        while (i <= m && j <= right) {
            if (a[i]<=a[j]){
                temp[k++] = a[i++];
            }else{
                temp[k++] = a[j++];
            }
        }
        //处理还剩下的
        while (i<=m){
            temp[k++] = a[i++];
        }
        while (j<=right){
            temp[k++] = a[j++];
        }
        for (int l = 0; l <= right - left; l++) {
            a[left+l]  = temp[l];
        }
    }

    public void mergeSort2(int[] a,int left, int right){
        if (left>=right){
            return;
        }
        int m = (left+right)/2;
        mergeSort2(a,left,m);
        mergeSort2(a,m+1,right);
        merge2(a,left,m,right);
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();

        int [] a = {3,2,4,5,0,1};
        mergeSort.mergeSort2(a,0,a.length-1);

        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }

    }


}
